#define _CRT_SECURE_NO_WARNINGS 1
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<unordered_map>
using namespace std;


  struct ListNode {
     int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
  class Solution {
  public:
      void reorderList(ListNode* head) {
          if (head == nullptr || head->next == nullptr || head->next->next == nullptr) return;
          ListNode* slow = head;
          ListNode* fast = head;
          while (fast && fast->next)
          {
              slow = slow->next;
              fast = fast->next->next;
          }
          ListNode* cur = slow->next;
          slow->next = nullptr;
          ListNode* hd = new ListNode(0);
          while (cur)
          {
              ListNode* tmp = cur->next;
              cur->next = hd->next;
              hd->next = cur;
              cur = tmp;
          }
          ListNode* tmp = hd->next;
          while (tmp)
          {
              ListNode* cur = tmp->next;
              tmp->next = head->next;
              head->next = tmp;
              head = tmp->next;
              tmp = cur;
          }
          delete hd;
          return;
      }
  };

int main() {
    return 0;
}